package com.example.algorithm.array;

/**
 * @author : zhy
 * 二分法
 * @since : 2022/7/21
 */
public class dichotomy {
    /**
     * 找到返回下标，找不到直接返回-1
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int right = nums.length-1;
        int left=0;
        //避免重复循环判断
        if(target<nums[0]||target>nums[right]){
            return -1;
        }
        while(left<=right)
        {
            //用这个方法求中位数，他可以防止数字溢出 其实也就是（right+left）/2
            //只是我写成int mid=(right-left)/2+left; 防止right+left数字溢出了
            int mid=(right-left)/2+left;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        dichotomy dichotomy = new dichotomy();
        int []num={1,2,3,4,6,7,8,9};
        int search = dichotomy.search(num, 5);
        if(search!=-1){
            System.out.println("找到啦，下标为"+search);
        }else {
            System.out.println("目标数字没有找到");
        }
    }
}
